//解决9*9的数独问题
//这里要用到的是二维回溯，分别回溯行和列
//二维回溯也是调用一次回溯函数，但要嵌套一个for循环，分别遍历行和遍历列
//这里的backtracking函数也使用bool类型
#include <vector>
using std::vector;
bool isValid(int row,int col,char val,vector<vector<char>>& board);


//二维回溯 用void意味着要递归两个维度，但这样做不到，因为递归只能向树枝深入，而不能既层向又树枝向
//故要用bool提供限制条件
//这里行列的转换不在递归中实现，而是通过循环实现
bool backtracking(vector<vector<char>>& board){
    for(int i=0;i<board.size();i++){                 //遍历行
        for(int j=0;j<board[i].size();j++){          //遍历列
            if(board[i][j]!='.') continue;
            for(char k='1';k<='9';k++){
                if(isValid(i,j,k,board)) {      //检测可不可以填这个数字，不可以就没必要填（剪枝）
                    board[i][j]=k;
                    if(backtracking(board)) return true;    //找到合适的一组（其实是一直递归直到填完数字都是true的时候）就直接返回，
                    board[i][j]='.';
                }
            }
            return false;
        }
    }
    return true;
}





bool isValid(int row,int col,char val,vector<vector<char>>& board){
    for(int i=0;i<board.size();i++){        //检测行重复
        if(val==board[row][i]) return false;
    }
    for(int i=0;i<board[col].size();i++){   //检测列重复
        if(val==board[i][col]) return false;
    }   
    
    //检测九宫格里有无重复
    //确定九宫格位置
    int startrow=(row/3)*3;
    int startcol=(col/3)*3;
    for(int i=startrow;i<startrow+3;i++){
        for(int j=startcol;j<startcol+3;j++){
            if(val==board[i][j]) return false;
        }
    }
    return true;
}


void solveSudoku(vector<vector<char>>& board) {
    backtracking(board);
}